1. Field of the Invention
The present invention relates to a logic synthesis for testability system which enables improvement in testability of a finite state machine (FSM) having an asynchronous reset state and also testability of an FSM having a state with a short distance from other state, and a logic synthesis method thereof.
2. Description of the Related Art
Unlike such design for testability as represented by the scan method in which testability of a logic circuit is enhanced after the designing of the logic circuit, a logic synthesis for a testability system is a system which executes optimization processing taking testability into consideration during logic circuit designing, that is, during logic synthesis, thereby synthesizing logic of a circuit which will have lower area overhead and a higher fault coverage than those achieved by design for testability methods and facilitate test-pattern generation.
One of conventional logic synthesis for testability systems is, for example, a system using a center state of a finite state machine (FSM) disclosed in "A Distance Reduction Approach to Design for Testability" (F. F. Hsu and J. H. Patel, The 13th IEEE VLSI Test Symposium, pp. 158-163, Apr. 30-May 3, 1995). In this system, a mean value of distances between all pairs of states is used as a testability measure of FSMs. A distance between pairs of states, assuming a pair of two states, a current state and a final transition goal state, is represented as a minimum number of clocks necessary for a transition from the current state to the final transition goal state. Being small in number denotes that the distance is short and Large in number denotes that the distance is long.
The reason why a mean value of distances can be a testability measure of an FSM is that a test-pattern length of a sequential circuit synthesized by FSMs depends on a distance between states. A test-pattern of a sequential circuit is made up by the repetition of a set of three sequences, a justification sequence, a fault activation sequence and a distinguish sequence. The justification sequence is an input pattern sequence for causing an internal state of a sequential circuit to transfer from a current internal state to an internal state required by the fault activation sequence. The fault activation sequence is an input pattern for propagating effects of faults to flip-flops (FFs) or external output terminals. The distinguish sequence is an input pattern sequence for propagating effects of faults propagated to FFs by the fault activation sequence to external output terminals. An internal state of a sequential circuit is denoted by a binary logical value vector held by FFs in the sequential circuit. With a sequential circuit having two FFs, for example, binary logical value vectors held by the FFs are four kinds, "00", "01", "10" and "11", each of which represents one internal state. When an internal state required by the fault activation sequence is equal to the current internal state, no justification sequence is necessary. When effects of faults are propagated to external output terminals by the fault activation sequence, no distinguish sequence is necessary. Since one state of an FSM corresponds to one internal state of the sequential circuit, transition of an internal state caused by the justification sequence is equivalent to transition of a state of the FSM.
Length of the justification sequence is therefore depends on a distance between states of an FSM, and reduction in distance between states of the FSM accordingly has the effect of reducing a justification sequence length and a sequential circuit test-pattern length. When a sequential circuit automatic test-pattern generation program is applied to a sequential circuit requiring a long justification sequence, test-pattern generation costs enormous time. Therefore, with a limitation put on a program execution time, if a fault occurs which costs much time for generating a test-pattern sequence, generation of a test-pattern for the fault might be interrupted midway in the processing to shift the processing to that for the generation of a test-pattern for another fault, whereby the number of faults detected is reduced to prevent acquisition of a satisfactory fault coverage in some cases. When a distance between states of an FSM is reduced, therefore, a resultant circuit obtained by logic synthesis is allowed to generate a test-pattern with a short sequence length and a high fault coverage in a short time period. An FSM with a small average distance value can be said to have high testability.
The logic synthesis for testability system using a center state, by regarding a state with the smallest sum of distances to other states as a center state and taking advantage of a distance from the center state to other states being short, adds a transition from each state to the center state to an FSM to generate a short path via the center state, thereby reducing a distance between pairs of states having a long state-to-state distance to synthesize a sequential circuit which can be tested with ease. Consider three states ST1, ST2 and ST3 in a predetermined FSM. It is assumed that a distance from ST1 to ST3 is "1", a distance from ST2 to ST3 is "3" and a distance from ST2 to ST1 is equal to or more than "2". Here, addition of a path, that is a transition, with a distance of "1" from ST2 to ST1 generates a path with a distance of "2" from ST2 to ST3 via ST1, resulting in reduction of the distance. This is a principle of distance reduction using a center state.
Next, a conventional logic synthesis for testability system will be detailed with reference to accompanying drawings. Although FSMs are classified into those of Mealy machine whose external output logical vecter is determined by a current state and an external input logical vecter and those of Moore machine whose external output logical value is determined only by a current state, a Moore machine FSM can be regarded as being of Mealy machine whose external output logical value is not dependent on an external input logical value and therefore description will be made with respect to a Mealy machine FSM.
FIG. 22 is a block diagram showing the entire structure of a conventional logic synthesis for a testability system. With reference to FIG. 22, the conventional logic synthesis for the testability system includes a library input unit 102 for reading a technology library for use in technology mapping and holding the same in a storage unit 101, a circuit input unit 103 for reading a description of a circuit as a target for logic synthesis and holding the same in the storage unit 101, a constraint input unit 104 for reading constraints such as area and delay and holding the same in the storage unit 101, an FSM extracting unit 105 for extracting an FSM when a circuit held in the storage unit 101 is expressed in a form other than a FSM, a testability improving unit 2201 for improving testability of a circuit represented by an FSM which is held in the storage unit 101, a state assignment unit 107 for assigning a binary logical value vector to a state of a circuit represented by an FSM which is held in the storage unit 101, an area optimization unit 108 for optimizing the area of a circuit held in the storage unit 101, a delay optimization unit 109 for optimizing the delay of a circuit held in the storage unit 101, a circuit output unit 110 for outputting a logic synthesis resultant circuit held in the storage unit 101, and the storage unit 101 for holding a circuit as a target for logic synthesis, a technology library and constraints. The testability improving unit 2201 includes a center state selecting unit 112 for selecting a center state among all states of an FSM as candidates, a transition adding unit 113 for adding a transition to a center state to an FSM, and a logic adding unit 114 for adding a logic circuit for generating a binary logical value vector assigned to a center state to a circuit whose states have been assigned.
Next, description will be made of operation of a conventional logic synthesis for testability system with reference to a flow chart shown in FIG. 23. FIG. 23 is a flow chart showing operation of a conventional logic synthesis for testability system. First, the library input unit 102 reads a technology library 121 and holds the same in the storage unit 101 (Step 2301), the circuit input unit 103 reads a circuit description 122 and holds the same in the storage unit 101 (Step 2302) and the constraints input unit 104 reads a constraint condition 123 and holds the same in the storage unit 101 (Step 2303). Next, the FSM extracting unit 105 extracts an FSM and holds the same in the storage unit 101 when the circuit held in the storage unit 101 is expressed in a form other than a FSM (Step 2304). Then, the center state selecting unit 112 of the testability improving unit 2201 selects a center state (Step 2305) and the transition adding unit 113 adds a transition from each state to the center state (Step 2306). Next, the state assignment unit 107 assigns a binary logical value vector to a state of the FSM held in the storage unit 101 (Step 2307). Then, the area optimization unit 108 conducts such area optimization independent of the technology library 121 as a two-level logic optimization or logic multi-level and area optimization technology mapping dependent on a technology using the technology library 121 (Step 2308). Next, the delay optimization unit 109 conducts delay optimization independent of the technology library 121 and delay optimization technology mapping dependent on a technology using the technology library 121 with respect to the circuit held in the storage unit 101 such that the designated constraint condition 123 is satisfied (Step 2309). Lastly, the circuit output unit 110 outputs a net list 124 of a logic synthesis resultant circuit held in the storage unit 101 (Step 2310).
Next, operation of the testability improving unit 2201 of the conventional logic synthesis for testability system will be described in detail. FIG. 24 is a state transition table of an FSM as a target for the testability improving unit 2201 which has no asynchronous reset state and is composed of two external input terminals, two external output terminals and six states, while FIG. 25 is a state transition graph of the FSM illustrated in FIG. 24. In FIG. 25, signs 301 to 306 denote states of the FSM and signs 307 to 320 denote transitions between transition states. Numeric values partitioned by a symbol "/" which are indicated near transition are an external input logical value as a condition for the occurrence of the transition and an external output logical value at the time of the occurrence of the transition. They are described in the form of "external input logical value/external output logical value". In FIG. 25, a transition 309, for example, denotes that if a logical value "01" is applied to the external input terminal when the current state is a state A301, transition to a state B302 occurs at the application of a next clock, whereby a logical value "01" is output to the external output terminal. The transition 309 is equivalent to a transition 2402 in the state transition table shown in FIG. 24. These relationships are established also for other states and transitions.
The operation of the center state selecting unit 112 is explained as follows. In the state-to-state distance calculation processing, the center state selecting unit 112 obtains distances between pairs of states. Obtained results are shown in FIG. 26. With reference to FIG. 26, since transition from the state A301 to the state B302 is made via the transition 309 in one clock, a value in the matrix in the A row, the B column in FIG. 26 will be "1". Since from the state A301 to a state E305, the shortest path is made in two clocks by a transfer to the state B302 via the transition 309 and then a transfer to the state E305 via a transition 312, a value in the matrix in the A row, the E column in FIG. 26 will be "2". Distances between the other states will be obtained in the same manner.
A mean value of thus obtained state-to-state distances is "2.16". Next, in the own distance resetting processing, a distance to its own state is set to "0". The results are shown in FIG. 27. Comparison between FIGS. 26 and 27 shows that the value in the matrix in the A row, the A column is "0" and as to the other states, values in the matrices in the same row, the same column are "0". Next, in the sum of distances calculation processing, a sum of distances from each state to other states is obtained. The results are shown in the column of SUM in FIG. 27. For example, a sum of distances from the state A301 to the other states is "7". Lastly, in the center state determination processing, a state with a smallest sum of distances to other states is selected as a center state. Based on the results shown in FIG. 27, the state A301 with the smallest sum is selected as a center state.
Next, the transition adding unit 113 adds a transition from every state to the center state and adds testability obtained by a distance reduction. FIG. 28 is a flow chart showing operation of the transition adding unit 113. With reference to FIG. 28, first in the center state controlling external input terminal adding processing at Step 2801, the unit 113 adds a center state controlling external input terminal to a circuit. The center state controlling external input terminal is an external input terminal for controlling a transition of an FSM, and when one of binary logical values is applied to the center state controlling external input terminal, the same transition as that of the original FSM takes places according to a logical value of other external input terminal and when the other of the binary logical values is applied, transition to the center state occurs regardless of a logical value of other external input terminal. The center state controlling external input terminal is here designated such that when a logical value of the center state controlling external input terminal is "0", the same transition as that of the original FSM occurs and when the logical value is "1", a transition to the center state occurs. Next, in the transition condition modifying processing at Step 2802, a logical value of an external input terminal as a transition condition is modified. More specifically, the logical value "0" of the center state controlling external input terminal causing the same transition as that of the original FSM is added to a logical value of the external input terminal as a transition condition. Lastly, in the processing for adding a transition to center state at Step 2803, a transition is added such that when the logical value of the center state controlling external input terminal is "1", a transition to the center state will occur regardless of a logical value of other external input terminal.
FIG. 29 is a state transition table of an FSM obtained after the completion of the processing by the transition adding unit 113, while FIG. 30 is a state transition graph of the FSM. The matrices with signs 2901 to 2914 in FIG. 29 denote transitions 2401 to 2414 each having a logical value of the center state controlling external input terminal added to transition conditions, while the matrices with signs 2915 to 2920 denote an added transition to the center state. A sign 3001 in FIG. 30 represents a transition 307 with a condition for a transition to the center state and a logical value of the center state controlling external input terminal added to transition conditions, while signs 3002 to 3010 represent transitions 308 to 316 each having a logical value of the center state controlling external input terminal added to transition conditions. A sign 3015 represents a transition 371 with a condition for a transition to the center state and a logical value of the center state controlling external input terminal added to transition conditions. Signs 3016 to 3018 represent transitions 318 to 320 each having a logical value of the center state controlling external input terminal added to transition conditions.
The transition 2402 is changed into the transition 2902 by the processing at Step 2801. The transition 2902 is obtained by adding a condition that a logical value of the center state controlling external input terminal is "0" to the transition 2402. The transition 2902 is equivalent to the transition 3003 in FIG. 30. This is also the case with other transitions. The transitions 2915 to 2920 are added by the processing at Step 2802.
The transition 2916 denotes that a transition to the state A301 selected as the center state occurs when the logical value of the center state controlling external input terminal is "1" at the current state of the state B302. This is also the case with other transitions. While a logical value of the external output terminal at the time of a transition to the center state is not particularly designated here but regarded as "don't care", some logical value may be designated. When the logical value is designated to be "don't care", an output logical value will be assigned later by the area optimization unit 108. In addition, the transition 2916 is equivalent to the transition 3015 in FIG. 30.
Since the transition 2901 and the transition 2915 have a current state and a next state coincident with each other, they are unitarily indicated as the transition 3001 in the state transition graph shown in FIG. 30. The transition 2912 and the transition 2919 are also unitarily indicated as the transition 3011 in FIG. 30.
For the purpose of confirming the effects of the above-described processing, results of the state-to-state distances obtained with respect to the FSM which is obtained based on FIG. 29 are shown in FIG. 31. For example, a distance from the state B304 to the state B302 indicated in the matrix in the D row, the B column in FIG. 26 is "5", while a distance indicated in the matrix in the D row, the B column in FIG. 31 is "2", which shows a distance reduction achieved by the addition of a transition to the center state. As to an average distance value, it is "2.16" in FIG. 26, while it is "1.16" in FIG. 31, which allows reduction in distance and improvement in testability to be confirmed.
Next, description will be made of operation of a conventional logic synthesis for testability system using the logic adding unit 114 which realizes the effect equivalent to that of adding a transition to the center state to an FSM by adding a logic circuit to a sequential circuit in which states of an FSM have been assigned. FIG. 32 is a flow chart showing operation of the conventional logic synthesis for testability system using the logic adding unit 114. The operation illustrated in the flow chart of FIG. 32, unlike the operation of the system using the transition adding unit 113 shown in the flow chart of FIG. 23, applies the state assignment unit 107 after the application of the center state selecting unit 112 (Steps 2305 and 2307) and then applies the logic adding unit 114 (Step 3201) but not the transition adding unit 113.
Next, operation of the conventional logic synthesis for testability system using the logic adding unit 114 will be described in detail. Since operation up to the processing by the center state selecting unit 112 at Step 2305 is the same as that of the system applying the transition adding unit 113 which has been described with reference to FIG. 23, no description will be made of the operation. In the processing at step 2307, the state assignment unit 107 assigns a binary logical value vector indicative of an internal state to each state. Since state assignment is a well-known technique, no description will be made thereof.
FIG. 33 is a diagram showing a sequential circuit obtained as a result of the processing by the state assignment unit 107. Three FFs are generated for representing six states. This is because the number of internal states expressible by FFs is 2 multiplied by the number of FFs and therefore the minimum number of FFs which can represent six states is three. As shown in FIG. 33, by the state assignment unit 107, the FSM is converted into a sequential circuit represented by a combinational circuit 3301 for receiving input of a logical value of an external input terminal 3312 and input of FF output logical values 3305 to 3307 to generate a logical value of an external output terminal 3313 and FF data input logic 3308 to 3310, FFs 3302 to 3304 for holding an internal state, FF output logical values 3305 to 3307, FF data input logic 3308 to 3310 for generating each bit of an internal state as an input logical value of an FF, a clock 3311 for FFs, the external input terminal 3312 and the external output terminal 3313.
FIG. 34 is a flow chart showing operation of the logic adding unit 114, while FIG. 35 is a sequential circuit obtained as a result of the application of the logic adding unit 114 to the sequential circuit illustrated in FIG. 33. It is assumed that to the state A301 selected by the center state selecting unit 112, a binary logical value vector "010" has been assigned as an internal state by the state assignment unit 107. In other words, a case where the logical value held by the FF3302 is "0", the logical value held by the FF3303 is "1" and the logical value held by the FF3304 is "0" is equivalent to the state A301. The effect equivalent to that produced by adding a transition to a center state can be therefore obtained by modifying the circuit such that when the logical value "0" is applied to the center state controlling input terminal, input logical values to the FFs 3302 to 3304 will be logical values of the FF data input logic 3308 to 3310 and when the logical value "1" is applied to the center state controlling input terminal, they will be represented by a binary logical value vector of "010".
With reference to FIG. 34, the logic adding unit 114 first adds the center state controlling external input terminal 3501 to the circuit (Step 3401). Then, determination is made whether an FF yet to be processed exists or not (Step 3402) and when there exists no FF yet to be processed, the processing by the logic adding unit 114 is completed. On the other hand, when there exist FFs yet to be processed, one of the FFs yet to be processed is extracted (Step 3403). It is assumed here that the FF3302 is first extracted. Next, determination is made which logical value of the center state is assigned to the FF (Step 3404) and when the logical value "0" is assigned, the routine proceeds to Step 3405 and when the logical value "1" is assigned, the routine proceeds to Step 3408. Since the logical value "0" is assigned to the FF3302, the routine proceeds to Step 3405 to determine whether a NOT element exists which generates reverse logic of the center state controlling external input terminal. Then, when a NOT element exists, the routine proceeds to Step 3407 and when no NOT element exists, the routine proceeds to Step 3407 via Step 3406. In this example, since no NOT element exists, the routine proceeds to Step 3406 to add a NOT element 3502 which generates reverse logic of the center state controlling external input terminal to the circuit and connect an input terminal of the NOT element 3502 with the center state controlling external input terminal 3501. Next, the unit 114 adds a two-input AND element 3503 and connects one input terminal of the element with the output terminal of the NOT element 3502 and the other input terminal with the FF data input logic 3308, disconnects the FF data input logic 3308 from the data input of the FF3302 and connects the output terminal of the two-input AND element 3503 to the data input terminal of the FF3302 (Step 3407). Thereafter, the routine returns to Step 3402. The foregoing modification results in that an input logical value to the data input terminal of the FF3302 will be expressed as "the center state controlling input terminal 3501*the FF data input logic 3308 (*denotes a logical product)", which enables a desired logical value to be applied to the FF3302.
Next, it is assumed that the FF3303 is selected at Step 3403. First, determination is made which logical value of the center state is assigned to the FF (Step 3404) and since the logical value "1" is assigned to the FF3303, the unit 114 adds a two-input OR element 3504, connects one input terminal of the element with the center state controlling external input terminal 3501 and the other input terminal with the FF data input logic 3309, disconnects the FF data input logic 3309 from the data input to the FF3303 and connects the output terminal of the two-input OR element 3504 to the data input terminal of the FF3303 (Step 3408). The foregoing modification results in that an input logical value to the data input terminal of the FF3303 will be expressed as "the center state controlling input terminal 3501+the FF data input logic 3309 (+denotes a logical sum)", which enables a desired logical value to be applied to the FF3303.
When the FF3304 is selected at Step 3303, processing is the same as that for the FF3302, except that the routine proceeds from Step 3405 directly to Step 3407 because the NOT element 3502 already exists, and therefore no description will be made of the processing here.
Although the foregoing description has been given of a case where a logic circuit which generates an internal state binary logical value vector assigned to a center state is implemented by using logic elements, it is also possible in actual application to use actual elements in the technology library 121 for use in technology mapping by the area optimization unit 108 and the delay optimization unit 109 or insert logic itself independent of the technology library 121.
In addition, although the description has been given of a case where the testability adding unit is executed immediately after the execution of the state assignment unit 107, logic synthesis may be conducted during the following execution of the area optimization unit 108 and the delay optimization unit 109 on condition that it is executed before the application of delay optimization which applies the re-timing technique of optimizing a delay by shifting an FF bridging over a combinational circuit. This is because re-timing alters the number of FFs and logic of FF data input in the circuit to lead to change of an internal state equivalent to an center state from a binary logical value vector assigned by the state assignment unit 107 to another binary logical value vector.
While the logic synthesis for testability system using a center state is directed to an FSM, it may be applied to an FSM extracted by the FSM extracting unit 105 from a sequential circuit expressed in other form than FSM such as a net list.
The above-described conventional logic synthesis for testability system has the following drawbacks.
The first drawback is that when an asynchronous reset state or a state with a short distance from the asynchronous reset state is selected as a center state, effects of testability improvement can not be obtained or if possible, the effects are very limited. The reason is that since the asynchronous reset state allows a transition from any state because of its function, state-to-state distances can not be reduced at all even by a new addition of a transition to the asynchronous reset state. Also as to a state with a short distance from the asynchronous reset state, since a path via the asynchronous reset state already exists, the effect of distance reduction is very little.
FIG. 3 is a state transition graph obtained in a case where the state A301 of the FSM shown in FIG. 25 is at an asynchronous reset state. An asynchronous reset transition 321 denotes that when an asynchronous reset control external input terminal RST has the logical value "1", transition to the state A301, which is an asynchronous reset state, occurs regardless of other external input terminals and clocks. Distances obtained with respect to this FSM are shown in FIG. 5. Although the number of clocks for a transition to the asynchronous reset state is "0", since one pattern is required for the transition, it is treated as requiring one clock, that is, as the distance of "1", for convenience. If selection of a center state is made here according to conventional art, the state A301 is selected as the center state. As a result, even the addition of a transition to the center state will not contribute to distance reduction and improvement in testability accordingly.
A second drawback is that when a state with a short distance from other states is selected as a center state, effects of testability improvement can not be obtained or if possible, the effects are very limited. The reason is that even if a transition to a state with a short distance from other states is newly added, reduction of state-to-state distances is slight because the distance is originally short.
FIG. 36 shows an FSM as a target for logic synthesis for testability. FIG. 37 shows results of state-to-state distances obtained in the FSM shown in FIG. 36, in which an average distance is "1.52". Application of the conventional logic synthesis for testability to this FSM results in selecting a state C3603 as a center state. Distances in the FSM obtained as a result of the addition of a transition to the state C3603 are shown in FIG. 38, in which an average distance is reduced to "1.41". FIG. 39 shows results of distances in the FSM illustrated in FIG. 36 which are obtained when a state E3605 is selected as the center state. In this case, the average distance is reduced down to "1.36", which is a greater reduction than that attained by the selection of any of the other states as a center state. The reason why the effect of distance reduction achieved by the state C3603 is smaller than that attained by the state E3605 is that since a distance from other state to the state C3603 is short, newly adding a transition from other state to the state C3603 to make the distance "1" will have little effect on distance reduction.